A conventional transmission chain is illustrated in FIG. 1. In a first step 12, the message to be transmitted 10 (original message) is used to calculate a cyclic redundancy check (CRC) block. The CRC technique is commonly used for detecting transmission errors by adding redundancy. The redundancy block is attached to the original message (by concatenating the binary sequences of the message and the redundancy block). Hereinafter, the message obtained by adding the redundancy block or by another preliminary transformation is designated “transformed message” in order to differentiate it from the original message. In the context of this document, the original message can be an informational message or any other message that can be represented in binary form.
The CRC block is a binary sequence of defined length, which is obtained by a hash of the original message. A CRC block of length n calculated on an original message of any given length permits the detection of all error bursts with a length that does not exceed n and a fraction of 1-2−n of the error bursts having a greater length. The CRC block is calculated by polynomial modulo 2 division. For this purpose, a polynomial of the message, hereinafter denoted M(x), is associated with the original message. The CRC block corresponds to the remainder R(x) of the polynomial modulo 2 division of M(x)·xn+1 by the generator polynomial of degree n+1, denoted G(x). The quotient of the division can be ignored. The degree of the remainder R(x) cannot be greater than the degree of G(x) minus one, i.e. n. Where necessary, O-valued bits are added to the remainder R(x) to create a CRC block of fixed length. In order to calculate the CRC block, one can use in particular a linear feedback shift register. The data packet formed by the original message, onto which has been attached the CRC block, is sometimes referred to as “code word”.
In the following step 14 the stuffing bits or stuffed bits that represent neither information nor redundancy are inserted in the transformed message. These stuffing bits are typically used to limit the number of consecutive bits of the same value and to introduce supplementary transitions. The supplementary transitions serve in particular to reduce the synchronization problems at the level of the receiver or to avoid the occurrence of binary sequences with a specific meaning (such as control sequences, for example). The HDLC protocol (acronym for High-level Data Link Control) uses stuffing bits to avoid the appearance of the flag for the time frame end (which in the case of HDLC corresponds to the binary sequence 01111110). According to the HDLC protocol, a 0 bit is inserted behind a sequence of five consecutive bits of value 1, thereby ensuring that the flag for the time frame end does not appear in the middle of a message. This is illustrated in FIG. 3. The stuffing bits can have the value 0 and/or 1, depending on the protocol specifications in question. In the case of HDLC or AIS (acronym for Automatic Identification System), the stuffing bits are always bits of value 0. It should also be noted that the concept of inserting stuffing bits must not be confused with the concept of padding that consists in the insertion of bits to arrive at a binary sequence of a predetermined length.
The transformed, stuffed message is then used to modulate (in the modulation step 16) a signal for the purposes of the transmission by the transmission channel 18. The modulation step 16 is possibly preceded by a channel coding (not shown in FIG. 1).
At the receiver side, the transmitted signal is demodulated (in the demodulation step 20) and decoded as needed. In order to recover the original message (the information bits), the stuffing bits are eliminated (step 22). In order to detect and/or correct the transmission errors, the receiver verifies the CRC of the message transmitted in step 24 before releasing the verified/corrected message (step 26) or an error message in the case where the correction would not be possible. Different methods are known for verifying the CRC. One of these methods consists in calculating the CRC on the received sequence of information bits and comparing it with the CRC of the transmitted message. A method that can be more easily implemented in hardware uses the property that the CRC of a binary sequence consisting of a message followed by its CRC is zero, and can be expressed as follows:CRC([data,CRC(data)])=0where CRC(.) designates the result of the calculation of CRC and [.,.] the concatenation of two binary sequences. Hence, with this method the CRC of the transmitted message is calculated (i.e. on the set of the information bits and the redundancy bits). If the result is 0 then the message is considered to have been correctly transmitted. Other methods exist that enable the position of an error bit to be detected. A method of this type is described, particularly in the article by B. McDaniel, An algorithm for error correcting cyclic redundance checks, C/C++ Users Journal, p. 6, 2003. Developments of this method enable several error bits to be corrected (cf. e.g. S. Babaie, A. K. Zadeh, S. H. Es-hagi, N. J. Nvimipour, Double bits error correction using CRC method, International Conference on Semantics, Knowledge and Grid, no 5, pp. 254-257, 2009 and C. Shi-yi and L. Yu-bai, Error correcting cycle redundancy checks based on confidence declaration, ITS Telecommunications Proceedings, no 6, pp. 511-514, 2006). However, all these methods assume that the stuffing bits were removed from the received message before they could be applied, which in practical terms greatly reduces their interest.
FIG. 2 shows a conventional transmission chain that differs from that of FIG. 1 in that the transformed message has been trellis coded in step 15 after stuffing bits had been inserted. At the receiver side, the transmitted signal is demodulated (in the demodulation step 20), e.g. by means of the Viterbi algorithm. The stuffing bits are eliminated after decoding but before verification of the CRC.